skdgdkgskhaskjdlajdkasjhd

package lesson;

public class RadixSort {

	public static void main(String[] args) {

	}

	static void radixSort(int[] a) {

		int max = maximum(a);
		int maxCount = digitsCount(max);

		for (int pos = 0; pos < maxCount; ++pos) {

			int[] counts = new int[10];
			int[] posSorted = new int[a.length];

			for (int i = 0; i < a.length; ++i) {
				int digit = kthDigit(a[i], pos);
				++counts[digit];
			}

			for (int i = 1; i < counts.length; ++i) {
				counts[i] += counts[i - 1];
			}

			for (int i = a.length - 1; i >= 0; --i) {
				int digit = kthDigit(a[i], pos);

				int position = counts[digit] - 1;
				posSorted[position] = a[i];

				--counts[digit];
			}

			for (int i = 0; i < a.length; ++i) {
				a[i] = posSorted[i];
			}
		}
	}

	static int kthDigit(int n, int k) {

		if (n == 0) {
			return 0;
		}

		if (k == 0) {
			return n % 10;
		} else {
			return kthDigit(n / 10, k - 1);
		}
	}

	static int digitsCount(int n) {
		if (n >= -9 && n <= 9) {
			return 1;
		} else {
			return 1 + digitsCount(n / 10);
		}
	}

	static int maximum(int[] a) {
		int max = a[0];

		for (int i = 0; i < a.length; ++i) {
			if (a[i] > max) {
				max = a[i];
			}
		}

		return max;
	}
}
